
#include "graph.h"
#include <stdlib.h>

/* G->n must be set already */
void read_degrees(FILE *f, GRAPH *G)
{
  long *degrees = calloc(G->n, sizeof(*degrees));
  long x, y;

  G->m = 0;
  while(fscanf(f, "%ld %ld\n", &x, &y) != EOF)
  {
    degrees[x]++;
    degrees[y]++;
    (G->m)++;
  }
  G->degrees = degrees;
}

void allocate(GRAPH *G)
{
  long *neighbours = malloc(2 * G->m * sizeof(long));
  long *next = neighbours;
  long i;

  G->links = malloc(G->n * sizeof(long **));
  for(i=0; i < G->n; i++)
  {
    G->links[i] = next;
    next += G->degrees[i];
  }
}

void read_links(FILE *f, GRAPH *G)
{
  long *next = malloc(G->n * sizeof(long));
  long i,x,y;
  
  for(i=0; i < G->n; i++)
    next[i] = 0;

  while(fscanf(f, "%ld %ld\n", &x, &y) != EOF)
  {
    G->links[x][next[x]++] = y;
    G->links[y][next[y]++] = x;
  }
  free(next);
}

GRAPH *graph_from_file(FILE *f, long n)
{
  GRAPH *G = malloc(sizeof(*G));

  G->n = n;
  read_degrees(f,G);
  rewind(f);
  allocate(G);
  read_links(f,G);
  return G;
}

int graph_to_file(FILE *f, GRAPH *G)
{
  long i, j;
  for(i=0; i < G->n; i++)
    for(j=0; j < G->degrees[i]; j++)
      printf("%ld %ld\n", i, G->links[i][j]);
}
